# date:20210209
from typing import List
import collections

# 双循环，超时。时间复杂度O(n*n)
class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        result = 0
        for i in range(len(A)-K+1):
            for j in range(i+K, len(A)+1):
                num = len(collections.Counter(A[i:j]))
                if num == K:
                    result += 1
                elif num > K:
                    break
        return result


class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        result = 0
        for i in range(len(A)-K+1):
            for j in range(i+K, len(A)+1):
                num = len(collections.Counter(A[i:j]))
                if num == K:
                    result += 1
                elif num > K:
                    break
        return result


model = Solution()
A = [1,2,1,2,3]
K = 2
print(model.subarraysWithKDistinct(A, K))

# [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
A = [1,2,1,3,4]
K = 3
print(model.subarraysWithKDistinct(A, K))


